import java.util.List;
import java.util.ArrayList;

public final class Hconstructiva2 extends Ejercicio
{ 
	public List <Integer> Vo1 = new ArrayList <Integer>();
	public List <Integer> Vo2 = new ArrayList <Integer>();
	private int cruces;
	
	protected Resultado DGIB
	(
			int n1, int v1[], int n2, int v2[], int m, Eje v1v2[],
			int np1, int vp1[], int np2, int vp2[], int mp, Eje vp1vp2[]
	){
		/*SEGUNDA HEURISTICA CONSTRUCTIVA:
		 Esta heuristica parte del grafo bipartito original y va agregando 
		 de a un nodo ubicandolo en la posicion donde provoque menor cantidad
		 de cruces*/
		
		Resultado res = new Resultado();
		
		int i; 
		int N1 = n1 + np1;
		int N2 = n2 + np2;
		
		Vo1 = new ArrayList <Integer>();
		Vo2 = new ArrayList <Integer>();
		
		cruces = cantidadCruces(v1,n1,v2,n2,v1v2,m);
		
		constructiva2
		(
				v1, n1,
				vp1, np1,
				vp2, np2,
				v1v2, m,
				vp1vp2, mp,
				v2, n2
		);
		
		int S1 [] = new int [N1];
		for(i = 0; i < N1; i++)
			S1[i] = Vo1.get(i);
		
		int S2 [] = new int [N2];
		for(i = 0; i < N2; i++)
			S2[i] = Vo2.get(i);
		
		res.kid = cruces;
		res.n_iv1 = N1;
		res.iv1 = S1; 
		res.n_iv2 = N2;
		res.iv2 = S2;
		
		return res;
	}

	public void constructiva2
	(
			int V1[], int n1,
			int VP1[], int np1,
			int VP2[], int np2,
			Eje V1V2[], int m,
			Eje VP1VP2[], int mp,
			int V2[], int n2
	){
		int n,k = 0,cruces_i = cruces,c = 0,cantejes = 0, h, v, j, i = 0;
		int M = m+mp;
		int best_i = 0;//guarda la posicion donde hay menos cruces hasta el momento
		int best_c = M*(M-1);//guarda el menor aumento que voy provocando con la insercion
		
		int e;
		
		for(h = 0;h < n1; h++)
		{
			e = V1[h];
			this.Vo1.add( h, e );
		}
		
		 n = Vo1.size();
		 List <Eje> ejes = new ArrayList <Eje>();
		
		 for(h = 0; h < m; h++)
		 {
			 ejes.add(h,V1V2[h]); 
			 cantejes++;
		 }
		 
		while( i <  np1 )
		{
			v = VP1[i];
			n = Vo1.size();
			
			Eje[] Ejestmp = new Eje[cantejes];
			
			for( h = 0; h < cantejes; h++ )
				Ejestmp[h] = ejes.get(h);
			
			for(j = 0; j < n+1; j++)//el lugar n + 1 existe?
			{
				Vo1.add(j, v);
				
				int[] Vtmp1 = new int[n+1];
				
				for( h = 0; h < n+1; h++ )
					Vtmp1[h] = Vo1.get(h);
				
				for(h = 0; h < mp; h++)
				{
					if(VP1VP2[h].origen == v)
					{
						if( esta(V2 ,VP1VP2[h].destino) )
						{
							c = CrucesDelEje(Vtmp1, n+1, V2, n2,Ejestmp, cantejes,VP1VP2[h]);
							cruces_i = cruces_i + c;
						}
					}
				}
				
				if(cruces_i < best_c )
				{
					best_i = j;
					best_c = cruces_i;
				}
				
					Vo1.remove(j);
			}
			
			Vo1.add(best_i, v);
			for(h = 0; h < mp; h++)
			{
				if(VP1VP2[h].origen == v)
				{
					if( esta(V2 ,VP1VP2[h].destino) )
					{
						ejes.add(cantejes,VP1VP2[h]);
						cantejes++;
					}
				}
			}
			i++;
			n++;
		}
	
		//n = Vo1.size();
		
		int[] Vtmp1 = new int[n];
		
		for( h = 0; h < n; h++ )
			Vtmp1[h] = Vo1.get(h);
		
		Eje[] Ejes = new Eje[cantejes];
		
		for( h = 0; h < cantejes; h++ )
			Ejes[h] = ejes.get(h);
	
		cruces = cruces_i;
		
		constructiva2
		(
			V2, n2,
			Ejes, cantejes,
			VP1VP2, mp,
			VP2, np2,
			Vtmp1, n, k
		);
}
	
	public void constructiva2
	(
			int V2[], int N2,
			Eje V1V2[], int m,
			Eje VP1VP2[], int mp,
			int VP2[], int np2,
			int IV1[], int N, int k
	){
		int n2,e,cruces_i = cruces,cantejes = 0, c=0, h, v, j, i = 0;
		int M = m+mp;
		int best_i = 0;//guarda la posicion donde hay menos cruces hasta el momento
		int best_c = M*(M-1);//guarda la menor cantidad de cruces que voy provocando con la inserciones
		
		for(h = 0; h< N2; h++)
		{
			e = V2[h];
			this.Vo2.add( h, e );
		}
		n2 = Vo2.size();
		
		List <Eje> ejes = new ArrayList <Eje>();
		 
		 for(h = 0; h < m; h++)
		 {
			 ejes.add(h,V1V2[h]);
			 cantejes++;
		 }
		 
		while( i <  np2)
		{
			v = VP2[i];
			n2 = Vo2.size();
			
			Eje[] Ejestmp = new Eje[cantejes];
			
			for( h = 0; h < cantejes; h++ )
				Ejestmp[h] = ejes.get(h);
			
			for(j = 0; j < n2+1; j++)//el lugar n + 1 existe?
			{
				Vo2.add( j, v);
				n2++;
				int[] Vtmp2 = new int[n2];
				
				for( h = 0; h < n2; h++ )
					Vtmp2[h] = Vo2.get(h);
				
				for(h = 0; h < mp; h++)
				{
					if(VP1VP2[h].destino == v)
					{
						if( esta(IV1 ,VP1VP2[h].origen) )
						{
							c = CrucesDelEje(IV1, N, Vtmp2, n2, Ejestmp, cantejes,VP1VP2[h]);
							cruces_i = cruces_i + c;
						}
					}
				}
				//hay que verificar/corregir esta parte..
				if(cruces_i < best_c)
				{
					best_i = j;
					best_c = cruces_i;
				}
				Vo2.remove(j);
				n2--;
			}
			
			Vo2.add(best_i, v);
			for(h = 0; h < mp; h++)
			{
				if(VP1VP2[h].destino == v)
				{
					if( esta(IV1 ,VP1VP2[h].origen) )
					{
						ejes.add(cantejes,VP1VP2[h]);
						cantejes++;
					}
				}
			}
			n2++;
			i++;
		}
		
		int[] Vtmp2 = new int[n2];
		
		for( h = 0; h < n2; h++ )
			Vtmp2[h] = Vo2.get(h);
		
		Eje[] Ejestmp = new Eje[cantejes];
		
		for( h = 0; h < cantejes; h++ )
			Ejestmp[h] = ejes.get(h);
		
		cruces = cantidadCruces(IV1, N, Vtmp2, n2, Ejestmp, cantejes);
	}
}